Veverica se nalazi u gornjem levom ćošku dvorišta kvadratnog oblika. Ona želi da se popne na drvo koje se nalazi u donjem desnom ćošku dvorišta i usput da pokupi barem jedan žir, pri čemu želi da se kreće samo dole ili desno.
Napisati program koji ispisuje broj mogućih putanja kojim veverica može doći do drveta. Vremenska i prostorna složenost treba da budu O(n2)
Sa standardnog ulaza se učitava dimenzija stranice dvorišta n, a zatim i matrica dimenzija n × n čiji su elementi 0 ili 1. Ukoliko je element 1 na tom mestu u dvorištu se nalazi žir.
Ispisati broj mogućih putanja kojim veverica može doći do drveta krećući se dole ili desno, a da pritom pokupi barem jedan žir.
4
0 0 1 0
1 0 0 0
0 1 0 0
1 0 1 018